The Royal Road Not Taken: A Re-examination of the Reasons for GA Failure on R1

Brian Howard¹ and John Sheppard^1,2

¹The Johns Hopkins University, 3400 N. Charles Street, Baltimore, MD 21218
itsbehoward@hotmail.com

²ARINC Engineering Services, LLC, 2551 Riva Road, Annapolis, MD 21401
jsheppar@arinc.com
jsheppa2@jhu.edu

Abstract. Previous work investigating the performance of genetic algorithms (GAs) has attempted to develop a set of fitness landscapes, called “Royal Roads” functions, which should be ideally suited for search with GAs. Surprisingly, many studies have shown that genetic algorithms actually perform worse than random mutation hill-climbing on these landscapes, and several different explanations have been offered to account for these observations. Using a detailed stochastic model of genetic search on R1, we attempt to determine a lower bound for the required number of function evaluations, and then use it to evaluate the performance of an actual genetic algorithm on R1.

LNCS 3102, p. 1208 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004